package main

import (
	"fmt"
	"math/rand"
	"sort"
)

// 第一题
// s1 := make([]int, 3, 4)
// s2 := append(s1, 1)
// 请问s1、s2内各有什么元素？
// s1: 0 0 0
// s2: 0 0 0 1

// s1修改一个元素会影响s2吗？
// 会影响，它们的底层数组是一样的

// s2修改一个元素会影响s1吗？
// s2修改索引为0-2的元素会影响s1，修改索引为3的元素不会影响s1

// s2再增加一个元素会怎么样？
// 由于容量不够，会进行扩容，因为新长度5小于2倍旧容量8，且旧容量小于256，所以会对旧容量进行翻倍，扩容后的cap为8

// 第二题
// 有一个数组 [1,4,9,16,2,5,10,15]，生成一个新切片，要求新切片元素是数组相邻2项的和
func newSlice() []int {
	arr := [...]int{1, 4, 9, 16, 2, 5, 10, 15}
	var ns []int
	var addElem []int
	for _, v := range arr {
		addElem = append(addElem, v)
		if len(addElem) == 2 {
			ns = append(ns, addElem[0]+addElem[1])
			addElem = []int{}
			addElem = append(addElem, v)
		}
	}
	return ns
}

// 第三题
// 数字重复统计
// 随机产生100个整数
// 数字的范围[-100, 100]
// 降序输出这些生成的数字并打印其重复的次数
func genRandInt() {
	ints := make([]int, 0, 100)
	numberCount := make(map[int]int, 100)
	for i := 0; i < 100; i++ {
		randNum := rand.Intn(101)
		operate := rand.Intn(2)
		if operate == 1 {
			randNum = -randNum
		}
		ints = append(ints, randNum)
		if _, ok := numberCount[randNum]; ok {
			numberCount[randNum]++
		} else {
			numberCount[randNum] = 1
		}
	}
	sort.Sort(sort.Reverse(sort.IntSlice(ints)))
	for _, v := range ints {
		fmt.Printf("%d   %d\n", v, numberCount[v])
	}
}

// 第四题
// 简述线性数据结构和哈希表优劣
// 线性表的实现有顺序表、链表、栈、队列

// 顺序表需要开辟一个连续的内存空间，每个元素占用的空间相同，可以通过索引直接计算出内存地址，所以查询和修改数据的时间复杂度为O(1)。
// 在首部或者中间插、删除数据会导致后面的元素移动，效率比较低，在尾部插入和删除的时间复杂度为O(1)。
// 插入的时候容量不够会导致扩容，所以尽量开辟足够的容量

// 链表是通过每个节点的指针链接下一个节点，所以数据可以分散内存中，查询数据的时间复杂度为O(n)，但是添加和删除的时间复杂度为O(1),
// 相对顺序表来说比较灵活，但是会占用更多的空间。

// 栈是LIFO的数据结构，只会在一端进行操作。插入和推出时间复杂度为O(1)。不能从首部和中间进行操作。

// 队列是FIFO的数据结构，在一端进行插入，一端进行推出，插入和推出的时间复杂度为O(1)。

// 哈希表保存的是kv对数据，通过key计算出的哈希值判断需要将kv对放入哪一个bucket中。哈希表的增删改查的操作都是O(1),效率很高，
// 但是在极端情况下，即所有的key都放入同一个bucket中，哈希表会退化为链表，删改查的操作时间复杂度会变为O(n)
